package binary_search;

/**题目：递增的二维数组,成Z字形递增，求某个值的下标位置
 * 二分搜索法的变体
 * @Author Gavin
 * @date 2022.01.02 10:43
 */
public class array_3 {
    /**
     * 解题思路：
     * 把二维数组看成一个一维数组来处理，中间就是如果把二维数组的下标
     * 转为一维数组的下标来定位元素
     */
    public static int[] solution(int[][] nums,int target){
        if(nums==null||nums.length==0||nums[0]==null||nums[0].length==0)
            return new int[]{-1,-1};
        int m=nums.length,n=nums[0].length;
        int low=0,high=m*n-1;
        while (low<=high){
            int mid=low+(high-low)/2;
            /**
             * 关键部分，把一维数组转换为二维的下标进行处理。
             * 这种方式只适用与z字型递增的二维数组，这里可以理解为
             * 每一行只能放n（列）个数，mid就可以放x个列（x个列就是第几行了）
             */
            int r=mid/n;//和列整除就为当前所在行
            int c=mid%n;//和列取模就为当前所在的列
            if(target<nums[r][c])high=mid-1;
            else if(target>nums[r][c])low=mid+1;
            else return new int[]{r,c};
        }
        return new int[]{-1,-1};
    }
}
